package stru1.day3;

/**
 * 121. 买卖股票的最佳时机
 */
public class Solution2 {
    public static void main(String[] args) {
        System.out.println(maxProfit(new int[]{7, 1, 5, 3, 6, 4}));
        System.out.println(maxProfit(new int[]{7, 6, 4, 3, 1}));
    }

    /**
     * 贪心算法，一次遍历，记录当前最低价和当前最高利润
     * 时间复杂度 O(n)
     * 空间复杂度 O(1)
     */
    public static int maxProfit(int[] prices) {
        int minPrice = prices[0];//最低价格
        int maxProfit = 0;//最大利润
        for (int i = 1; i < prices.length; i++) {  //卖出在买进之前 所以只按顺序遍历一次
            //将最低价格和当前价格比较，低的为新的最低价格
            minPrice = Math.min(prices[i], minPrice);
            //将当前价格减去最低价格的值与最大利润比较，高的为新的最大利润
            maxProfit = Math.max(prices[i] - minPrice, maxProfit);
        }
        //返回最大利润
        return maxProfit;
    }
}
